<?php
/**
 * @title 785. 判断二分图 - 迭代+哈希
 * @author start2004
 */

class Solution {

    /**
     * @param Integer[][] $graph
     * @return Boolean
     */
    function isBipartite($graph) {
        /**
         * @since 2020-08-14 集合0, 集合1
         */
        $hash = [0=>[], 1=>[]];

        /**
         * @since 2020-08-14 迭代
         */
        while($graph){
            /**
             * @since 2020-08-14 第一次, 或者无法延生更多节点
             * @since 2020-08-14 抛出一个节点
             */
            $key0 = key($graph);

            /**
             * @since 2020-08-14 默认集合0
             */
            $hash[0][$key0] = 1;

            /**
             * @since 2020-08-14 边的另外一点归属集合1
             */
            $nexts = [];
            foreach ($graph[$key0] as $key1){
                $hash[1][$key1] = 1;
                $nexts[] = $key1;
            }
            unset($graph[$key0]);

            /**
             * @since 2020-08-14 起点1, 终点0, 后面身份会发生交换, 使用集合ab
             */
            $a = 1;
            $b = 0;

            /**
             * @since 2020-08-14 延生查找
             */
            while($nexts){
                $nextsTmp = [];

                /**
                 * @since 2020-08-14 遍历, 延生的B点集合, 防止重复检查
                 */
                $keysB = [];

                /**
                 * @since 2020-08-14 遍历
                 */
                foreach ($nexts as $keyA){
                    /**
                     * @since 2020-08-14 延生的点B
                     */
                    foreach ($graph[$keyA] as $keyB){
                        $keysB[$keyB] = 1;
                    }

                    /**
                     * @since 2020-08-14 移除A点
                     */
                    unset($graph[$keyA]);
                }

                /**
                 * @since 2020-08-14 检查延生的B点集合
                 */
                foreach ($keysB as $keyB=>$val){
                    /**
                     * @since 2020-08-14 延生的点B, 不能在集合A中
                     */
                    if(isset($hash[$a][$keyB])){
                        return false;
                        break;
                    } else {}

                    /**
                     * @since 2020-08-14 延生的点B, 是新点进入下一轮检查
                     * @since 2020-08-14 有hash检查, 不会重复
                     */
                    if(!isset($hash[$b][$keyB])){
                        $hash[$b][$keyB] = 1;
                        $nextsTmp[] = $keyB;
                    } else {}
                }


                /**
                 * @since 2020-08-14 交换身份
                 */
                list($a, $b) = [$b, $a];

                /**
                 * @since 2020-08-14 下次迭代
                 */
                $nexts = $nextsTmp;
            }
        }

        /**
         * @return
         */
        return true;
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.16_2.php
 */
$datas = [
    [[1,3], [0,2], [1,3], [0,2]],
    [[1,2,3], [0,2], [0,1,3], [0,2]],
    [[1],[0,3],[3],[1,2]],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->isBipartite($data);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
